<!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta name="robot" content="index,follow">
<title>Module bct - binary cell tree module - Forth Foundation Library</title>
</head>
<body>
<h2>bct - binary cell tree module</h2>
<h3>Module Description</h3>
<p>The bct module implements an unbalanced binary tree with the key and data
cell based. The implementation is non-recursive.
</p>
<h3>Module Words</h3>
<dl>
</dl>
<h4>Binary tree structure</h4>
<dl>
<dt><a name="word1"><b>bct%</b>	( -- n )</dt>
<dd>Get the required space for a bct variable</dd>
</dl>
<h4>Tree creation, initialisation and destruction</h4>
<dl>
<dt><a name="word2"><b>bct-init</b>	( bct -- )</dt>
<dd>Initialise the tree</dd>
<dt><a name="word3"><b>bct-(free)</b>	( bct -- )</dt>
<dd>Free the nodes from the heap</dd>
<dt><a name="word4"><b>bct-create</b>	( "&lt;spaces&gt;name" -- ; -- bct )</dt>
<dd>Create a named binary tree in the dictionary</dd>
<dt><a name="word5"><b>bct-new</b>	( -- bct )</dt>
<dd>Create a new binary tree on the heap</dd>
<dt><a name="word6"><b>bct-free</b>	( bct -- )</dt>
<dd>Free the tree node from the heap</dd>
</dl>
<h4>Member words</h4>
<dl>
<dt><a name="word7"><b>bct-length@</b>	( bct -- u )</dt>
<dd>Get the number of elements in the tree</dd>
<dt><a name="word8"><b>bct-empty?</b>	( bct -- flag )</dt>
<dd>Check for an empty tree</dd>
<dt><a name="word9"><b>bct-compare@</b>	( bct -- xt )</dt>
<dd>Get the compare execution token for comparing keys</dd>
<dt><a name="word10"><b>bct-compare!</b>	( xt bct -- )</dt>
<dd>Set the compare execution token for comparing keys</dd>
</dl>
<h4>Tree words</h4>
<dl>
<dt><a name="word11"><b>bct-clear</b>	( bct -- )</dt>
<dd>Delete all nodes in the tree</dd>
<dt><a name="word12"><b>bct-insert</b>	( x1 x2 bct -- )</dt>
<dd>Insert data x1 with key x2 in the tree</dd>
<dt><a name="word13"><b>bct-delete</b>	( x1 bct -- false | x2 true )</dt>
<dd>Delete key x1 from the tree, return the cell data x2</dd>
<dt><a name="word14"><b>bct-get</b>	( x1 bct -- false | x2 true )</dt>
<dd>Get the data x2 related to key x1 from the tree</dd>
<dt><a name="word15"><b>bct-has?</b>	( x1 bct -- flag )</dt>
<dd>Check if the key x1 is present in the tree</dd>
<dt><a name="word16"><b>bct-execute</b>	( i*x xt bct -- j*x )</dt>
<dd>Execute xt for every key and data in the tree</dd>
<dt><a name="word17"><b>bct-execute?</b>	( i*x xt bct -- j*x flag )</dt>
<dd>Execute xt for every key and data in the tree until xt returns true</dd>
</dl>
<h4>Inspection</h4>
<dl>
<dt><a name="word18"><b>bct-dump</b>	( bct -- )</dt>
<dd>Dump the tree node structure</dd>
</dl>
<h3>Examples</h3>
<pre>
include ffl/bct.fs
include ffl/bci.fs
include ffl/str.fs
include ffl/enm.fs


\ Example1: store mountain height in a binary tree with numerical keys

\ The mountain enumeration

begin-enumeration
  enum: MountEverest
  enum: MontBlanc
  enum: MountElbrus
  enum: Vaalserberg
end-enumeration


\ Create the binary tree on the heap and store it in the heights variable

bct-new value heights


\ Add the mountain heights in the tree; the key is the mountain enum value

8300 MountEverest heights bct-insert
4819 MontBlanc    heights bct-insert
5642 MountElbrus  heights bct-insert


\ Find a mountain height in the tree

MontBlanc heights bct-get [IF]
  .( Mount:mont blanc height:) . cr
[ELSE]
  .( Mount:mont blanc not in tree.) cr
[THEN]

Vaalserberg heights bct-get [IF]
  .( Mount:vaalserber height:) . cr
[ELSE]
  .( Mount:vaalserberg not in tree.) cr
[THEN]


\ Free the heights tree from the heap

heights bct-free



\ Example2: store mountain height in a binary tree with string keys


\ Create the binary tree in the dictionary

bct-create mountains


\ Setup the compare word for comparing the mountain names

: mount-compare  ( str str - n = Compare the two mountain names )
  str^ccompare
;

' mount-compare mountains bct-compare!


\ Add the mountain heights to the binary tree; the key is the mountain name in a (unique) dynamic string

8300 str-new dup s" mount everest" rot str-set  mountains bct-insert
4819 str-new dup s" mont blanc"    rot str-set  mountains bct-insert
5642 str-new dup s" mount elbrus"  rot str-set  mountains bct-insert


\ Find a mountain height in the binary tree

str-new value mount-name

s" mont blanc" mount-name str-set

mount-name mountains bct-get [IF]
  .( Mount:)        mount-name str-get type 
  .(  height:)      . cr 
[ELSE]
  .( Mount:) mount-name str-get type .(  not in tree.) cr
[THEN]


s" vaalserberg" mount-name str-set

mount-name mountains bct-get [IF]
  .( Mount:)        mount-name str-get type 
  .(  height:)      . cr 
[ELSE]
  .( Mount:) mount-name str-get type .(  not in tree.) cr
[THEN] 


\ Word for printing the mountain heights

: mount-emit ( x x -- = Print mountain )
  str-get type ."  --&gt; " . cr
;


\ Print all mountain heights

' mount-emit mountains bct-execute       \ Execute the word mount-emit for all entries in the tree


\ Example binary tree iterator

\ Create the tree iterator in the dictionary

mountains bci-create mount-iter          \ Create an iterator named mount-iter on the mountains tree


\ Using the iterator

mount-iter bci-first [IF]
  .( First mount:) mount-iter bci-key drop str-get type 
  .(  height:)     . cr 
[ELSE]
  .( No first mountain.) cr
[THEN]

mount-iter bci-last [IF]
  .( Last mount:) mount-iter bci-key drop str-get type 
  .(  height:)    . cr
[ELSE]
  .( No last mountain.) cr
[THEN]


\ Cleanup the tree

mountains bct-clear
</pre>
<hr>
<div align="center">generated 24-Jul-2010 by <b>ofcfrth-0.10.0</b></div>
</body>
</html>
